package com.kitty.record.kittyalgorithm.audition;

/**
 //编写一个函数，检查输入的链表是否是回文的。
 //
 // 示例 1：
 // 输入： 1->2
 //输出： false
 //
 // 示例 2：
 // 输入： 1->2->2->1
 //输出： true
 //
 // 进阶：
 //你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
 * @Author SHEN
 * @Date 2020/11/26
 */
public class LeetCode0206 {
    public static void main(String[] args) {
        ListNode listNode = new ListNode(1);
        listNode.next = new ListNode(1);
        listNode.next.next = new ListNode(2);
        listNode.next.next.next = new ListNode(1);
        System.out.println(isPalindrome(listNode));
    }

    public static boolean isPalindrome(ListNode head) {

        ListNode positive = head;
        ListNode reversion = head;
        reversion = reverse(reversion);
        while (positive != null) {
            //然后比较，判断节点值是否相等
            if (positive.val != reversion.val)
                return false;
            positive = positive.next;
            reversion = reversion.next;
        }
        return true;
    }
    //反转同时复制一个链表
    public static ListNode reverse(ListNode h) {
        ListNode prev = null;
        while (h != null) {
            ListNode n = new ListNode(h.val);
            n.next = prev;
            prev = n;
            h = h.next;
        }
        return prev;
    }

    //直接反转链表，不创建新的链表
    public static ListNode reverse1(ListNode h) {
        ListNode prev = null;
        while (h != null) {
            ListNode next = h.next;
            h.next = prev;
            prev = h;
            h = next;
        }
        return prev;
    }




    private static class ListNode {
      private int val;
      private ListNode next;
      ListNode(int x) { val = x; }
    }
}
